home *** CD-ROM | disk | FTP | other *** search
/ Hyper Stacks 1994 May / Hyper Stacks (Pacific HiTech)(1994)[Mac].iso / Organization / TEX ƒ / indexTEXfile 0.5.c < prev    next >
Text File  |  1988-09-04  |  44KB  |  1,728 lines
  1. /* new indexTEXfile XFCN for TEX dataspace manager
  2.  * ^z - 880901-0904
  3.  * this early version needs much work to make it friendlier -- should
  4.  * never try to do ExitToShell(), for instance!!
  5.  *
  6.  * call the XFCN as 'indexTEXfile()' ... it returns with nothing
  7.  * if all goes well, and an error message (if possible) otherwise...
  8.  *
  9.  *    ---------------------------------------------------------------
  10.  *
  11.  * copyright 1988 by Mark "^z" Zimmermann - all rights reserved.
  12.  * (Symantec/Think Technologies may also have copyrights on portions.)
  13.  * All standard legalistic disclaimers are included herewith by reference.
  14.  * (If, for example, your use of this software causes a thermonuclear
  15.  * war and the destruction of civilization (as we know it), I am
  16.  * not responsible.)  Use the program at your own risk!!!  I have
  17.  * never lost any data with it -- but there are no guarantees in life.
  18.  *
  19.  * This XFCN was developed using Think's Lightspeed C.  It is available
  20.  * for nonexclusive licensing at a cost of 2% of retail price
  21.  * per distributed copy of any for-sale software
  22.  * that uses it (as of Sept. 1988).  My HyperCard stack using this XFCN,
  23.  * "TEX", is available via CompuServe, Arpanet, and other media.
  24.  *
  25.  ***********************************************************************
  26.  *   Individual users of TEX should send a $10 license fee to me at    *
  27.  *   the below address. The corporate license fee is $40 per copy in   *
  28.  *   simultaneous use.                                                 *
  29.  ***********************************************************************
  30.  *
  31.  * In exchange for your license fee, you get:
  32.  *    - information about extensions and enhancements to this program
  33.  *        as they are come out;
  34.  *    - free support and advice on its use;
  35.  *    - copies of new versions for the cost of media and reproduction;
  36.  *    - a nice warm feeling knowing that you are supporting further
  37.  *        research into massive free-text dataspace tool-building.
  38.  *
  39.  * Be a part of the adventure!  If you can't afford cash, take the time
  40.  * to write me a nice letter about how you're using CONTEXT, or send a
  41.  * disk with your ideas/suggestions/modifications to the stack.
  42.  * 
  43.  * All monies received are used to enhance this software and to pay for
  44.  * creation and distribution expenses.  Comparable "commercial" free-text
  45.  * database products cost hundreds or thousands of dollars.  You have
  46.  * something precious here -- take advantage of it, please!  Build upon
  47.  * my work, extend it, and share your results with the community of
  48.  * researchers.
  49.  *
  50.  * I am very proud of this software.  I have chosen to distribute it
  51.  * at nominal cost, so that it can be more widely used and can help
  52.  * more people.  Please join me!
  53.  *
  54.  * For further information, and for license fee payments, write:
  55.  *    Mark ^Zimmermann
  56.  *    9511 Gwyndale Drive
  57.  *    Silver Spring, MD  20910
  58.  *    USA
  59.  *
  60.  * Be sure to enclose a STAMPED, SELF-ADDRESSED ENVELOPE if you want
  61.  * to receive a timely reply!
  62.  *
  63.  * Electronic addresses:
  64.  *     science@nems.arpa
  65.  *     [75066,2044] CompuServe
  66.  *     tel. 301-565-2166
  67.  *    ---------------------------------------------------------------
  68.  */
  69.  
  70.  
  71. /* header files to include...
  72.  */
  73.  
  74. #include <MacTypes.h>
  75. #include <EventMgr.h>
  76. #include <OSUtil.h>
  77. #include <FileMgr.h>
  78. #include <WindowMgr.h>
  79. #include <StdFilePkg.h>
  80. #include <HyperXCmd.h>
  81.  
  82. /* sort on 28 characters --  long enough to avoid truncation of most real
  83.  * words, and short enough to save some space in the *.k files
  84.  */
  85. #define KEY_LENGTH  28
  86.  
  87. /* my standard structure for the index_keys file
  88.  */
  89. typedef struct
  90.   {
  91.     char kkey[KEY_LENGTH];
  92.     long ccount;
  93.   }  KEY_REC;
  94.  
  95. /* my standard structure for simple I/O buffers ...
  96.  */
  97. typedef struct
  98.   {
  99.     char *zbufbase;
  100.     char *zbufp;
  101.     long zbufcounter;
  102.     long zbufsize;
  103.     int  zbuffilep;
  104.     int  zbufitemsize;
  105.   }  ZBUF;
  106.  
  107.  
  108. /* merge this many files at each stage of the merging operation for index
  109.  * building ... 2 means a binary merge, etc. ... one needs to have at least
  110.  * 5 + 2 * NMERGE I/O buffers around:  for each of NMERGE files, there is
  111.  * a *.k keys file and a *.p pointers file; plus there must be a single
  112.  * output *.k and a single output *.p file; plus there is the need for stdin,
  113.  * stdout, and stderr to be open as well.  Thus, I have found that a 4-way
  114.  * merge (NMERGE = 4) works pretty nicely....
  115.  */
  116. #define NMERGE 4
  117.  
  118. #ifndef TRUE
  119. #define TRUE   1
  120. #endif
  121.  
  122. #ifndef FALSE
  123. #define FALSE  0
  124. #endif
  125.  
  126. #ifndef NULL 
  127. #define NULL   0
  128. #endif
  129.  
  130. #ifndef EOF
  131. #define EOF  (-1)
  132. #endif
  133.  
  134.  
  135. /* define these to allow use of global variables in my XFCNs; a
  136.  * Lightspeed C necessity, apparently...
  137.  */
  138.  
  139. #define SetUpA4()        asm  {    move.l a4,-(sp)        \
  140.                                 move.l a0,a4    }
  141.  
  142. #define RestoreA4()        asm  {    move.l (sp)+,a4    }
  143.  
  144.  
  145. /* --------------function prototypes ----------------------- */
  146.  
  147.  
  148. pascal void main (XCmdBlockPtr paramPtr);
  149. int zGetFile (Str255 *fileNamePtr, int *volRefNumPtr, long fileType);
  150. void returnErrorMsg (XCmdBlockPtr paramPtr, char *msg);
  151. void give_msg (char *msg);
  152. void beepWait (void);
  153. long atol (char *s);
  154. int putNum (char *ans, long num);
  155. int strlen (char *s);
  156. char *strcpy (char *s1, char *s2);
  157. void create_zbuffer (int n, long bufsize, int buffile, int bufitemsize,
  158.                         ZBUF zbuffer[]);
  159. char *next_input_item (int n, ZBUF zbuffer[]);
  160. void load_zbuffer (int n, ZBUF zbuffer[]);
  161. char *next_output_item (int n, ZBUF zbuffer[]);
  162. void flush_zbuffer (int n, ZBUF zbuffer[]);
  163. int build_indices (long zbufsiz, int doc_file, int vRef0, int pass_number);
  164. void init_filter_table (void);
  165. char *make_buf (long bufsiz);
  166. long load_doc_buffer (char *doc, long doc_bufsiz, char **ptr, int doc_file);
  167. int zgetc (int refNum);
  168. char *strncpy(char *s1, char *s2, int n);
  169. void nway_merge_kpfiles (int ink[], int inp[], int outk, int outp, int n,
  170.                             long zbufsiz);
  171. void copy_ptr_recs (int inzbuf, long count, int outzbuf, ZBUF zbuffer[]);
  172. void copy_key_rec (char *kkey, long ccount, int outzbuf, ZBUF zbuffer[]);
  173. int merge_not_finished (KEY_REC *kr[], int n);
  174. int smallest_key (KEY_REC *kr[], int n);
  175. int merge_indices (long zbufsiz, int doc_file, int vRef0,
  176.             int file_number, int generation_number, Str255 doc_filename);
  177. long write_sorted_files (char *doc, char **ptr, long nwords, long offset,
  178.         long zbufsiz, int pass_number, int vRef0);
  179. int is_new_word (char *w0, char *w1);
  180. void write_new_key (char *p, char *kp);
  181. long file_size (int refnum);
  182. int open_inkfile (int file_num, int vRef0, int generation_number);
  183. int open_inpfile (int file_num, int vRef0, int generation_number);
  184. void fix_oddball_file_name (int vRef0, int generation_number,
  185.             int file_number);
  186. void fix_final_file_names (Str255 doc_filename, int vRef0,
  187.             int generation_number);
  188. int open_outkfile (int vRef0, int generation_number, int file_number);
  189. int open_outpfile (int vRef0, int generation_number, int file_number);
  190. void remove_used_infiles (int n, int vRef0, int generation_number,
  191.             int file_number);
  192. void close_infiles (int ink[], int inp[], int n);
  193. int open_kfile (int vRef0, int pass_number);
  194. int open_pfile (int vRef0, int pass_number);
  195. long zftell (int refnum);
  196. void zqsort (char **first, char **last);
  197. int compare_ptrs (char **p1, char **p2);
  198. int zstrcmp (char *s1, char *s2);
  199.  
  200.  
  201. /* standard table to filter lower-case characters to capitals (if possible)
  202.  * for sorting into alphabetical order ... my best estimates of what to
  203.  * do for foreign characters in the Apple character set ... consider
  204.  * using international utilities someday to do the sorting better...
  205.  */
  206.  
  207. char filter_table[256] =
  208.   {       0,   0,   0,   0,   0,   0,   0,   0,
  209.        0,   0,   0,   0,   0,   0,   0,   0,
  210.          0,   0,   0,   0,   0,   0,   0,   0,
  211.          0,   0,   0,   0,   0,   0,   0,   0,
  212.        0,   0,   0,   0,   0,   0,   0,   0,
  213.        0,   0,   0,   0,   0,   0,   0,   0,
  214.      '0', '1', '2', '3', '4', '5', '6', '7',
  215.      '8', '9',   0,   0,   0,   0,   0,   0,
  216.        0, 'A', 'B', 'C', 'D', 'E', 'F', 'G',
  217.      'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
  218.      'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',
  219.      'X', 'Y', 'Z',   0,   0,   0,   0,   0,
  220.        0, 'A', 'B', 'C', 'D', 'E', 'F', 'G',
  221.      'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
  222.      'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',
  223.      'X', 'Y', 'Z',   0,   0,   0,   0,   0,
  224.     0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,
  225.     0xCB,0x89,0x80,0xCC,0x81,0x82,0x83,0x8F,
  226.     0x90,0x91,0x92,0x93,0x94,0x95,0x84,0x97,
  227.     0x98,0x99,0x85,0xCD,0x9C,0x9D,0x9E,0x86,
  228.        0,   0,   0,   0,   0,   0,   0,0xA7,
  229.        0,   0,   0,   0,   0,   0,0xAE,0xAF,
  230.        0,   0,   0,   0,   0,0xB5,0xC6,0xB7,
  231.     0xB8,0xB8,   0,0xBB,0xBC,0xBD,0xAE,0xAF,
  232.        0,   0,   0,   0,   0,   0,0xC6,   0,
  233.        0,   0,   0,0xCB,0xCC,0xCD,0xCE,0xCE,
  234.        0,   0,   0,   0,   0,   0,   0,   0,
  235.     0xD8,   0,   0,   0,   0,   0,   0,   0,
  236.        0,   0,   0,   0,   0,   0,   0,   0,
  237.        0,   0,   0,   0,   0,   0,   0,   0,
  238.        0,   0,   0,   0,   0,   0,   0,   0,
  239.        0,   0,   0,   0,   0,   0,   0,   0  } ;
  240.  
  241.  
  242. /* ----------------------main program------------------------- */
  243.  
  244. pascal void main (paramPtr)
  245.   XCmdBlockPtr paramPtr;
  246.   {
  247.     Str255 doc_filename;
  248.     char info[128];
  249.     Ptr testzbufsiz;
  250.     WindowRecord w_record;
  251.     WindowPtr info_window;
  252.     Rect b_rect;
  253.     Handle answer;
  254.     int doc_file, vRef0, pass_number, generation_number,
  255.         prev_gen_number, file_number, i;
  256.     long zbufsiz, doc_filesize, grow;
  257.  
  258.     SetUpA4();
  259.     
  260.     if (paramPtr->paramCount != 0)
  261.       {
  262.          returnErrorMsg (paramPtr,
  263.               "{Sorry, wrong number of parameters in indexTEXfile call!}");
  264.           RestoreA4();
  265.           return;
  266.       }
  267.  
  268.     /* see how much memory we can get for our zbuffers ... */
  269.     MaxApplZone();
  270.     zbufsiz = MaxMem (&grow) - 32768;
  271.     zbufsiz /=  (2 * NMERGE + 2);
  272.     zbufsiz = zbufsiz - zbufsiz % (sizeof(KEY_REC) * sizeof(long));
  273.      
  274.     if (zbufsiz < sizeof(KEY_REC) * sizeof(long) ||
  275.         (testzbufsiz = NewPtr (zbufsiz * (2 * NMERGE + 2))) == NULL)
  276.       {
  277.          returnErrorMsg (paramPtr,
  278.               "{Sorry, not enough free memory to build an index!}");
  279.           RestoreA4();
  280.           return;
  281.       }
  282.       DisposPtr (testzbufsiz);
  283.  
  284.     /* set up a window to give user feedback during indexing */
  285.     b_rect.top = 30;
  286.     b_rect.left = 12;
  287.     b_rect.bottom = 332;
  288.     b_rect.right = 500;
  289.     info_window = NewWindow (&w_record, &b_rect, "\p", (Boolean)1,
  290.         dBoxProc, (WindowPtr)-1, (Boolean)0, (long)0);
  291.     ShowWindow (info_window);
  292.     SetPort (info_window);
  293.     TextFont (0);
  294.     give_msg ("\pGreetings!  Please choose a text file to be indexed...");
  295.  
  296.     if (! zGetFile (&doc_filename, &vRef0, 'TEXT'))
  297.       {
  298.         DisposeWindow (info_window);
  299.           RestoreA4();
  300.         return;
  301.       }
  302.     
  303.     i = FSOpen (doc_filename, vRef0, &doc_file);
  304.     if (i != noErr && i != opWrErr)
  305.       {
  306.         give_msg ("\pSorry, error opening the file!  Click mouse to exit...");
  307.         beepWait ();
  308.         CloseWindow (info_window);
  309.           RestoreA4();
  310.           return;
  311.       }
  312.     
  313.     give_msg ("\pBeginning to build index subfiles — please be patient...");
  314.     
  315.     pass_number = 0;
  316.     while (build_indices (zbufsiz, doc_file, vRef0, pass_number))
  317.         ++pass_number;
  318.  
  319.     give_msg ("\pBeginning merge generation #1 — please be patient...");
  320.  
  321.     file_number = 0;
  322.     generation_number = 0;
  323.     do
  324.       {
  325.         prev_gen_number = generation_number;
  326.         generation_number = merge_indices (zbufsiz, doc_file, vRef0,
  327.                         file_number, generation_number, doc_filename);
  328.         if (generation_number == prev_gen_number)
  329.             file_number += NMERGE;
  330.         else
  331.             file_number = 0;
  332.       }
  333.     while (generation_number >= 0);
  334.  
  335.     FSClose (doc_file);
  336.     give_msg ("\pIndexing completed! — click mouse to exit...");
  337.     beepWait ();
  338.     CloseWindow (info_window);
  339.     RestoreA4();
  340.     return;
  341.   }
  342.  
  343.  
  344. /* this routine, adapted from the Lightspeed C 'MiniEdit' example, does
  345.  * the standard files dialog routine to get the name of the text file
  346.  * of the dataspace; other file names are gotten from that by putting
  347.  * a '.k' or a '.p' at the end.  This routine returns 1 if all is well,
  348.  * or 0 if the user cancels out...
  349.  */
  350.  
  351. int zGetFile (fileNamePtr, volRefNumPtr, fileType)
  352.   Str255 *fileNamePtr;
  353.   int *volRefNumPtr;
  354.   long fileType;
  355.   {
  356.     SFTypeList myFileTypes;
  357.     Point SFGwhere;
  358.     SFReply myReply;
  359.     register int i;
  360.  
  361.     SFGwhere.v = 90;
  362.     SFGwhere.h = 82;
  363.     myFileTypes[0] = fileType;
  364.     
  365.     SFGetFile (SFGwhere, "\p", 0L, 1, myFileTypes, 0L, &myReply);
  366.     
  367.     if (myReply.good)
  368.       {
  369.         for (i = *myReply.fName; i >= 0; --i)
  370.             (*fileNamePtr)[i] = myReply.fName[i];
  371.         *volRefNumPtr = myReply.vRefNum;
  372.         return (1);
  373.       }
  374.     else
  375.         return (0);
  376.   }
  377.  
  378.  
  379. /* function to set the return value of the XFCN to a chosen error msg;
  380.  * if there isn't enough free memory to give us a Handle to the msg,
  381.  * beep a bunch and then return!
  382.  */
  383.  
  384. void returnErrorMsg (paramPtr, msg)
  385.   XCmdBlockPtr paramPtr;
  386.   char *msg;
  387.   {
  388.     Handle answer;
  389.     int msgLength;
  390.     
  391.     SysBeep (10);
  392.     msgLength = strlen (msg);
  393.     if ((answer = NewHandle (1 + msgLength)) == NULL)
  394.       {
  395.         SysBeep (10);
  396.         SysBeep (10);
  397.         SysBeep (10);
  398.         SysBeep (10);
  399.         SysBeep (10);
  400.         return;
  401.       }
  402.  
  403.     strcpy (*answer, msg);
  404.     paramPtr->returnValue = answer;
  405.     return;
  406.   }
  407.  
  408.  
  409. /* tiny routine to put a message into my message window.... takes in a
  410.  * PASCAL type string and displays it nicely....
  411.  * modified 880612 to make the window scroll text up....
  412.  */
  413.  
  414. void give_msg (msg)
  415.   char *msg;
  416.   {
  417.     Rect b_rect;
  418.     RgnHandle theRgn;
  419.     
  420.     b_rect.top = b_rect.left = 0;
  421.     b_rect.bottom = 302;
  422.     b_rect.right = 488;
  423.     
  424.     theRgn = NewRgn ();
  425.     ScrollRect (&b_rect, 0, -15, theRgn);
  426.     DisposeRgn (theRgn);
  427.     
  428.     MoveTo (4, 295);
  429.     DrawString (msg);
  430.     
  431.     return;
  432.   }
  433.  
  434.  
  435. /* function to beep and then wait for a mouse click before returning...
  436.  * delay for 2 ticks to debounce the mouse button a bit .... flush
  437.  * events to avoid spurious clicks hanging around....
  438.  */
  439.  
  440. void beepWait ()
  441.   {
  442.       long tickcount;
  443.  
  444.       SysBeep (10);
  445.       while (! Button())
  446.         ;
  447.     Delay (2L, &tickcount);
  448.     while (Button())
  449.         ;
  450.     Delay (2L, &tickcount);
  451.     FlushEvents (everyEvent, 0);
  452.     return;
  453.   }
  454.  
  455.  
  456. /* function to convert alphabetic string to a long integer ... from LSC
  457.  * library.... simplified to avoid using isspace() & isdigit() ....
  458.  */
  459.  
  460. long atol (s)
  461.   register char *s;
  462.   {
  463.     register char signflag = 0;
  464.     register long r = 0;
  465.  
  466.     while ((*s == ' '))
  467.         s++;
  468.         
  469.     if (*s == '-')
  470.       {
  471.         signflag = 1;
  472.         s++;
  473.       }
  474.     else if (*s == '+')
  475.          s++;
  476.  
  477.     while (*s >= '0' && *s <= '9') 
  478.         r = r * 10 + (*s++ - '0');
  479.     
  480.     return (signflag ? -r : r);
  481. }
  482.  
  483.  
  484.  
  485. /* function to convert a number into a string and put it into the chosen
  486.  * target place ... returns the number of characters stored ...
  487.  * based on K&R p. 60 example of itoa().... ^z ... note, NO TERMINAL
  488.  * '\0' in the string that is built!
  489.  */
  490.  
  491. int putNum (ans, num)
  492.   register char *ans;
  493.   register long num;
  494.   {
  495.     register int i, j;
  496.     int s, result;
  497.     
  498.     i = 0;
  499.     s = 1;
  500.     if (num < 0)
  501.       {
  502.         num = -num;
  503.         s = -1;
  504.       }
  505.     
  506.     do
  507.           ans[i++] = num % 10 + '0';
  508.     while ((num /= 10) > 0);
  509.     
  510.     if (s < 0)
  511.         ans[i++] = '-';
  512.     result = i;
  513.     
  514.     for (--i, j = 0; j < i; ++j, --i)
  515.       {
  516.           s = ans[i];
  517.           ans[i] = ans[j];
  518.           ans[j] = s;
  519.       }
  520.  
  521.     return (result);
  522.   }
  523.  
  524.  
  525. /* function to determine the length of a string ... standard thing,
  526.  * adapted from the LSC library, and K&R p.98 ....
  527.  */
  528.  
  529. int strlen (s)
  530.   register char *s;
  531.   {
  532.     char *s0 = s;
  533.  
  534.     while (*s++)
  535.         ;
  536.     return (s - s0 - 1);
  537.   }
  538.  
  539.  
  540. /* function to copy a string from one place to another, in a rather
  541.  * obvious fashion ... adapted from the LSC library, and K&R p.101 ....
  542.  */
  543.  
  544. char *strcpy (s1, s2)
  545.   register char *s1, *s2;
  546.   {
  547.     char *s = s1;
  548.     
  549.     while (*s1++ = *s2++)
  550.         ;
  551.     return (s);
  552.   }
  553.  
  554.  
  555. /* -------------------buffer-related functions-----------------*/
  556.  
  557. /* function to create a zbuffer and set its parameters appropriately
  558.  */
  559.  
  560. void create_zbuffer (n, bufsize, buffile, bufitemsize, zbuffer)
  561.   int n, bufitemsize;
  562.   long bufsize;
  563.   int buffile;
  564.   ZBUF zbuffer[];
  565.   {
  566.     zbuffer[n].zbufbase = make_buf (bufsize);
  567.     zbuffer[n].zbufp = zbuffer[n].zbufbase;
  568.     zbuffer[n].zbufcounter = 0;
  569.     zbuffer[n].zbufsize = bufsize;
  570.     zbuffer[n].zbuffilep = buffile;
  571.     zbuffer[n].zbufitemsize = bufitemsize;
  572.   }
  573.  
  574.  
  575. /* function to return a pointer to the next item in a chosen input
  576.  * buffer 'n'; it reloads the buffer if necessary ... returns NULL
  577.  * pointer when there's nothing left in the file ...
  578.  */
  579.  
  580. char *next_input_item (n, zbuffer)
  581.   int n;
  582.   ZBUF zbuffer[];
  583.   {
  584.     char *result;
  585.     
  586.     if (zbuffer[n].zbufcounter == 0)
  587.         load_zbuffer (n, zbuffer);
  588.     
  589.     zbuffer[n].zbufcounter -= zbuffer[n].zbufitemsize;
  590.     if (zbuffer[n].zbufcounter >= 0)
  591.       {
  592.         result = zbuffer[n].zbufp;
  593.         zbuffer[n].zbufp += zbuffer[n].zbufitemsize;
  594.         return (result);
  595.       }
  596.     else
  597.         return (NULL);
  598.   }
  599.  
  600.  
  601. /* function to load the nth zbuffer appropriately ... it resets the buffer
  602.  * pointers, etc. ... 
  603.  */
  604.  
  605. void load_zbuffer (n, zbuffer)
  606.   int n;
  607.   ZBUF zbuffer[];
  608.   {
  609.     long nread;
  610.     OSErr err;
  611.  
  612.     nread = zbuffer[n].zbufsize;
  613.     err = FSRead (zbuffer[n].zbuffilep, &nread, zbuffer[n].zbufbase);
  614.  
  615.     zbuffer[n].zbufp = zbuffer[n].zbufbase;
  616.     zbuffer[n].zbufcounter = nread;
  617.     
  618.     if (err != noErr && err != eofErr)
  619.       {
  620.         give_msg ("\pSorry, fatal error loading a buffer -- click mouse to exit, then reboot!");
  621.         beepWait ();
  622.           RestoreA4();
  623.         ExitToShell ();
  624.       }
  625.     
  626.     return;
  627.   }
  628.  
  629.  
  630. /* function to return a pointer to the right place to store the next
  631.  * output item for the nth zbuffer ... when the buffer becomes full,
  632.  * it flushes it to disk, resets pointers, etc.
  633.  */
  634.  
  635. char *next_output_item (n, zbuffer)
  636.   int n;
  637.   ZBUF zbuffer[];
  638.   {
  639.     char *result;
  640.  
  641.     if (zbuffer[n].zbufcounter == zbuffer[n].zbufsize)
  642.         flush_zbuffer (n, zbuffer);
  643.     
  644.     result = zbuffer[n].zbufp;
  645.     zbuffer[n].zbufp += zbuffer[n].zbufitemsize;
  646.     zbuffer[n].zbufcounter += zbuffer[n].zbufitemsize;
  647.     return (result);
  648.   }
  649.  
  650.  
  651. /* function to flush out a zbuffer to the disk ... 
  652.  */
  653.  
  654. void flush_zbuffer (n, zbuffer)
  655.   int n;
  656.   ZBUF zbuffer[];
  657.   {
  658.     long chars_written;
  659.     
  660.     if (zbuffer[n].zbufcounter == 0)
  661.         return;
  662.  
  663.     chars_written = zbuffer[n].zbufcounter;
  664.     if (FSWrite (zbuffer[n].zbuffilep, &chars_written,
  665.                 zbuffer[n].zbufbase) != noErr || chars_written == 0)
  666.       {
  667.         give_msg ("\pSorry, fatal error flushing a buffer -- click mouse to exit, then reboot!");
  668.         beepWait ();
  669.           RestoreA4();
  670.         ExitToShell ();
  671.       }
  672.     
  673.     zbuffer[n].zbufp = zbuffer[n].zbufbase;
  674.     zbuffer[n].zbufcounter = 0;
  675.   }
  676.   
  677.  
  678. /* ------------------index-building functions------------------*/
  679.  
  680. int build_indices (zbufsiz, doc_file, vRef0, pass_number)
  681.   long zbufsiz;
  682.   int doc_file, vRef0, pass_number;
  683.   {
  684.     long doc_bufsiz, offset, nwords, ndistinctwords;
  685.     char *doc, **ptr, info[128];
  686.     int i;
  687.  
  688.     doc_bufsiz = 2 * NMERGE * zbufsiz / 3 - KEY_LENGTH;
  689.     doc = make_buf (doc_bufsiz + KEY_LENGTH);
  690.     
  691.     ptr = (char **)make_buf (doc_bufsiz * 2);
  692.  
  693.     offset = zftell (doc_file);    
  694.     
  695.     nwords = load_doc_buffer (doc, doc_bufsiz, ptr, doc_file);
  696.  
  697.     if (nwords == 0)
  698.       {
  699.         DisposPtr (doc);
  700.         DisposPtr (ptr);
  701.         return (FALSE);
  702.       }
  703.     
  704.     zqsort (ptr, ptr + nwords);
  705.  
  706.     ndistinctwords = write_sorted_files (doc, ptr, nwords, offset, zbufsiz,
  707.                             pass_number, vRef0);
  708.     
  709.     DisposPtr (doc);
  710.     DisposPtr (ptr);
  711.  
  712.     strncpy (info + 1, "Index subfile #", 15);
  713.     i = 16 + putNum (info + 16, pass_number + 1);
  714.     strncpy (info + i, ":  ", 3);
  715.     i += 3;
  716.     i += putNum (info + i, nwords);
  717.     strncpy (info + i, " total words, ", 14);
  718.     i += 14;
  719.     i += putNum (info + i, ndistinctwords);
  720.     strncpy (info + i, " distinct words.", 16);
  721.     i += 16;
  722.     info[0] = i - 1;
  723.     give_msg (info);
  724.     
  725.     return (TRUE);
  726.   }
  727.  
  728. /* ---------functions to load text from document file filter it-------- */
  729.  
  730.  
  731. /* function to create a buffer for me to use...
  732.  */
  733.  
  734. char *make_buf (bufsiz)
  735.   long bufsiz;
  736.   {
  737.     char *buf;
  738.     
  739.     buf = NewPtr (bufsiz);
  740.  
  741.     if (buf == 0)
  742.       {
  743.         give_msg ("\pSorry, fatal error creating a buffer -- click mouse to exit, then reboot!");
  744.         beepWait ();
  745.           RestoreA4();
  746.         ExitToShell ();
  747.       }
  748.     
  749.     return (buf);
  750.   }
  751.  
  752.  
  753. /* function to load the document buffer ... bring in doc_bufsiz
  754.  * characters, and then enough more to finish out the final word,
  755.  * followed by a terminal delimiter .... as the characters are scanned
  756.  * filter them appropriately (change delimiters to '\0's) and
  757.  * build the pointer array in memory to the first character of each
  758.  * word ... return the total number of words that were
  759.  * read in to the buffer (zero if we're finished with the file)
  760.  *
  761.  * ... note that one must be sure to pull in and throw away
  762.  * any excess characters beyond KEY_LENGTH in the final word, so that
  763.  * the remaining fragment doesn't show up as the first "word" in the
  764.  * next chunk of the file....
  765.  *
  766.  * For maximum speed and efficiency, use a hybrid approach:  do a
  767.  * big buffer-sized chunk of the file first, then take one character at
  768.  * a time to finish off....
  769.  */
  770.  
  771. long load_doc_buffer (doc, doc_bufsiz, ptr, doc_file)
  772.   register char *doc, **ptr;
  773.   long doc_bufsiz;
  774.   int doc_file;
  775.   {
  776.     int  i, err;
  777.     register int c, in_a_word = FALSE;
  778.     char **ptr0, *end_doc_buf;
  779.      
  780.      ptr0 = ptr;
  781.      
  782.      err = FSRead (doc_file, &doc_bufsiz, doc);
  783.      if (err != noErr && err != eofErr)
  784.       {
  785.         give_msg ("\pSorry, fatal error reading text -- click mouse to exit, then reboot!");
  786.         beepWait ();
  787.           RestoreA4();
  788.         ExitToShell ();
  789.       }
  790.  
  791.      end_doc_buf = doc + doc_bufsiz;
  792.      
  793.      while (doc < end_doc_buf)
  794.       {
  795.         c = filter_table[*(unsigned char *)doc];
  796.  
  797.         if (c == '\0')
  798.             in_a_word = FALSE;
  799.          else if (! in_a_word)
  800.           {
  801.             *ptr++ = doc;
  802.             in_a_word = TRUE;
  803.           }
  804.  
  805.          *doc++ = c;
  806.        }
  807.      
  808.      if (err != eofErr && doc == end_doc_buf && in_a_word)
  809.       {
  810.           for (i = 0; i < KEY_LENGTH; ++i)
  811.            {
  812.              c = zgetc (doc_file);
  813.              if (c == EOF)
  814.                {
  815.                  *doc++ = '\0';
  816.                  break;
  817.                }
  818.              c = filter_table[c];
  819.              if (c == '\0')
  820.                {
  821.                  *doc++ = '\0';
  822.                  break;
  823.                }
  824.              *doc++ = c;
  825.            }
  826.          if (i == KEY_LENGTH)
  827.              while ((c = zgetc (doc_file)) != EOF && filter_table[c])
  828.                 ;
  829.        }
  830.      
  831.      return (ptr - ptr0);
  832.   }
  833.  
  834.  
  835. /* my function to replace getc() ... give up and call it EOF on any error
  836.  * at all, at this point! ... note also that we must return the UNSIGNED
  837.  * character read in, to handle Mac special characters properly....
  838.  */
  839.  
  840. int zgetc (refNum)
  841.   int refNum;
  842.   {
  843.       unsigned char readbuf[1];
  844.       long count = 1;
  845.       
  846.     if (FSRead (refNum, &count, readbuf) == noErr)
  847.         return (readbuf[0]);
  848.     else
  849.         return (EOF);
  850.   }
  851.  
  852.  
  853. /* function to copy a string of length up to n from s2 to s1.... from
  854.  * LSC library ...
  855.  */
  856.  
  857. char *strncpy (s1, s2, n)
  858.   register char *s1, *s2;
  859.   register int n;
  860.   {
  861.     char *s0 = s1;
  862.     
  863.     if (n > 0)
  864.     {
  865.         while (n-- && (*s1++ = *s2++));
  866.     
  867.         while (n > 0)
  868.         {    /* pad out to n chars -- H&S specs it this way... */
  869.         
  870.             *s1++ = '\0';
  871.             n--;
  872.         }
  873.     }
  874.         
  875.     return (s0);
  876. }
  877.  
  878. /* ------functions to merge key and ptr files-------------------- */
  879.  
  880.  
  881. /* function to do the real work of merging sorted k & p
  882.  * files into a single sorted file...
  883.  *
  884.  * Procedure is as follows:
  885.  *
  886.  *    Compare the current key records from each of the N files to be merged.
  887.  *    Take the smallest of the keys (or, if there is a tie, take the one
  888.  *    from the earlier file number) and write its pointer records out to
  889.  *    the *.p file for the next generation.  If the key is a new one, that
  890.  *    is, if it differs from the previous key, write out the previous key
  891.  *    word and the value for cumulative_counts to the *.k file, and reset
  892.  *    the previous key's value to that of the current key.  Then repeat
  893.  *    this whole procedure, until all the input files are exhausted.
  894.  *
  895.  *    The above works provided that we are careful in choosing the smallest
  896.  *    key and never let a file that has been exhausted (reached EOF) win a
  897.  *    comparison.  The function smallest_key does that properly below, since
  898.  *    a file that is at EOF has returned a NULL pointer for its key_rec...
  899.  *
  900.  *  For each file, the variable prev_cc[i] holds the previous value of
  901.  *    cumulative_counts for that file, so that we can determine how
  902.  *    many ptr_recs to write out by doing a simple subtraction.
  903.  *
  904.  * Buffer numbering scheme:  the Kth input file has zbuffer #K
  905.  *    for its keys and zbuffer #(K+n) for its pointers; the output
  906.  *    buffers are zbuffers #(2*n) for keys and #(2*n+1) for pointers.
  907.  */
  908.  
  909. void nway_merge_kpfiles (ink, inp, outk, outp, n, zbufsiz)
  910.   int ink[], inp[], outk, outp, n;
  911.   long zbufsiz;
  912.   {
  913.     int i;
  914.     KEY_REC *kr[NMERGE], prev_key;
  915.     long prev_cc[NMERGE], out_cc;
  916.     ZBUF zbuffer[NMERGE * 2 + 2];    
  917.     
  918.     for (i = 0; i < n; ++i)
  919.         prev_cc[i] = 0;
  920.     out_cc = 0;
  921.     
  922.     for (i = 0; i < n; ++i)
  923.       {
  924.         create_zbuffer (i, zbufsiz, ink[i], sizeof(KEY_REC), zbuffer);
  925.         create_zbuffer (i + n, zbufsiz, inp[i], sizeof(long), zbuffer);
  926.       }
  927.     create_zbuffer (2 * n, zbufsiz, outk, sizeof(KEY_REC), zbuffer);
  928.     create_zbuffer (2 * n + 1, zbufsiz, outp, sizeof(long), zbuffer);
  929.     
  930.     for (i = 0; i < n; ++i)
  931.         kr[i] = (KEY_REC *)next_input_item (i, zbuffer);
  932.     
  933.     i = smallest_key (kr, n);
  934.     strncpy (prev_key.kkey, kr[i]->kkey, KEY_LENGTH);
  935.     
  936.  
  937.     while (merge_not_finished (kr, n))
  938.       {
  939.         i = smallest_key (kr, n);
  940.         if (zstrcmp (prev_key.kkey, kr[i]->kkey))
  941.           {
  942.             copy_key_rec (prev_key.kkey, out_cc, 2 * n, zbuffer);
  943.             strncpy (prev_key.kkey, kr[i]->kkey, KEY_LENGTH);
  944.           }
  945.         copy_ptr_recs (i + n, kr[i]->ccount - prev_cc[i], 2 * n + 1, zbuffer);
  946.         out_cc += kr[i]->ccount - prev_cc[i];
  947.         prev_cc[i] = kr[i]->ccount;
  948.         kr[i] = (KEY_REC *)next_input_item (i, zbuffer);
  949.       }
  950.     
  951.     copy_key_rec (prev_key.kkey, out_cc, 2 * n, zbuffer);
  952.     
  953.     flush_zbuffer (2 * n, zbuffer);
  954.     flush_zbuffer (2 * n + 1, zbuffer);
  955.     for (i = 0; i < 2 * n + 2; ++i)
  956.         DisposPtr (zbuffer[i].zbufbase);
  957.   }
  958.  
  959.  
  960. /* function to copy a chosen number of ptr_recs (longs) from one file
  961.  * to another ... used in merging two files by merge_kpfiles() above....
  962.  * revised and simplified to use zbuffers....870902 ... ^z
  963.  *
  964.  * revised to call check_events pretty often, for multifinder
  965.  * politeness.... -- removed 871211 ^z for HC XFCN stuff
  966.  */
  967.  
  968. void copy_ptr_recs (inzbuf, count, outzbuf, zbuffer)
  969.   int inzbuf, outzbuf;
  970.   long count;
  971.   ZBUF zbuffer[];
  972.   {
  973.     long *inp, *outp;
  974.  
  975.     for ( ; count > 0; --count)
  976.       {
  977.         inp = (long *)next_input_item (inzbuf, zbuffer);
  978.         outp = (long *)next_output_item (outzbuf, zbuffer);
  979.         *outp = *inp;
  980.       }
  981.   }
  982.  
  983.  
  984. /* function to write a key record including kkey (key word) and ccount
  985.  * (cumulative_count) to an output file...
  986.  */
  987.  
  988. void copy_key_rec (kkey, cc, outzbuf, zbuffer)
  989.   char *kkey;
  990.   long cc;
  991.   int outzbuf;
  992.   ZBUF zbuffer[];
  993.   {
  994.     KEY_REC *outp;
  995.  
  996.     outp = (KEY_REC *)next_output_item (outzbuf, zbuffer);
  997.     strncpy (outp->kkey, kkey, KEY_LENGTH);
  998.     outp->ccount = cc;
  999.   }
  1000.  
  1001.  
  1002. /* simple function to see if we are not yet finished with all of the input
  1003.  * files coming in to the merge operation ... signified by at least one of
  1004.  * the key pointers being non-NULL....
  1005.  */
  1006.  
  1007. int merge_not_finished (kr, n)
  1008.   KEY_REC *kr[];
  1009.   register int n;
  1010.   {
  1011.     register int i;
  1012.     
  1013.     for (i = 0; i < n; ++i)
  1014.         if (kr[i] != NULL)
  1015.             return (TRUE);
  1016.     
  1017.     return (FALSE);
  1018.   }
  1019.  
  1020.  
  1021. /* function to determine the smallest of the n keys pointed to by the
  1022.  * kr[] vector of pointers to KEY_RECs ... note that a NULL ptr ranks
  1023.  * after any other...also note that in case of a tie, the smaller
  1024.  * value of i is the one to return (for a stable merging sort)
  1025.  */
  1026.  
  1027. smallest_key (kr, n)
  1028.   KEY_REC *kr[];
  1029.   register int n;
  1030.   {
  1031.     register int i, smallest;
  1032.  
  1033.     for (i = 0; i < n; ++i)
  1034.         if (kr[i] != NULL)
  1035.           {
  1036.             smallest = i;
  1037.             break;
  1038.           }
  1039.  
  1040.     for (i = smallest + 1; i < n; ++i)
  1041.         if (kr[i] != NULL)
  1042.             if (zstrcmp (kr[smallest]->kkey, kr[i]->kkey) > 0)
  1043.                 smallest = i;
  1044.  
  1045.     return (smallest);
  1046.   }
  1047.  
  1048. /* ---------------function to merge index files------------- */
  1049.  
  1050. /* file "merge_indices.c" ... by ^z -- 870823-...
  1051.  * function to merge sorted indices together repeatedly until finished
  1052.  * with them all in a single set of *.k/*.p files ...
  1053.  *
  1054.  * The merging strategy is straightforward enough:
  1055.  *    Let "g" denote the generation_number and "f" denote the file_number.
  1056.  *    Temporary file names begin with the letter z, which is then followed
  1057.  *    by a generation number (decimal), the letter k or p (standing for
  1058.  *    key or ptr, respectively), and then the file number (decimal).  Thus,
  1059.  *    the file "z0k0" is the keys file #0 for generation #0 (the starting,
  1060.  *    pre-merging, generation), file "z2p3" is the ptr file #3 for generation
  1061.  *    #2, etc.
  1062.  *
  1063.  * (The following discussion is specifically for a 2-way merge ... but
  1064.  * the generalization for N-way merging is straightforward.)
  1065.  *
  1066.  *    On a given call to merge_indices, the following may happen:
  1067.  *        - files zgkf/zgpf and zgk(f+1)/zgp(f+1) are merged into files
  1068.  *            z(g+1)k(f/2)/z(g+1)p(f/2), and then the parent files are
  1069.  *            deleted;
  1070.  *        - file zgkf isn't found, which means we are done with this
  1071.  *            generation and must go on to the next;
  1072.  *        - file zgk(f+1) isn't found, which means that either we are
  1073.  *            completely done with the merging work (if f=0) and just
  1074.  *            have to rename the files zgkf/zgpf into the correct final
  1075.  *            names (that is, doc_filename.k/doc_filename.p), or else
  1076.  *            (if f>0) we have an odd number of files for this level
  1077.  *            of merging, and therefore just have to rename zgkf/zgpf
  1078.  *            to z(g+1)k(f/2)/z(g+1)p(f/2).
  1079.  */
  1080.  
  1081. /* modified 871224 to get rid of static variables used for generation_number
  1082.  * and file_number ... instead, make the function return the upcoming
  1083.  * generation_number, and let the caller reset the file_number to zero
  1084.  * when the generation_number returned differs from the input number, or
  1085.  * increment the file_number by NMERGE when still on same generation.
  1086.  * Also, when all finished, return an illegal (negative) generation_number
  1087.  * value.  ^z
  1088.  */
  1089.  
  1090. int merge_indices (zbufsiz, doc_file, vRef0, file_number,
  1091.                         generation_number, doc_filename)
  1092.   long zbufsiz;
  1093.   int doc_file, vRef0, file_number, generation_number;
  1094.   Str255 doc_filename;
  1095.   {
  1096.     int ink[NMERGE], inp[NMERGE], outk, outp;
  1097.     long inwords, indistinctwords, outdistinctwords;
  1098.     int i, n;
  1099.     char info[128];
  1100.     
  1101.     for (n = 0; n < NMERGE; ++n)
  1102.       {
  1103.         ink[n] = open_inkfile (file_number + n, vRef0, generation_number);
  1104.         if (ink[n] == NULL)
  1105.             break;
  1106.         inp[n] = open_inpfile (file_number + n, vRef0, generation_number);
  1107.       }
  1108.     
  1109.     if (file_number + n == 1)
  1110.       {        
  1111.         close_infiles (ink, inp, n);
  1112.         fix_final_file_names (doc_filename, vRef0, generation_number);
  1113.         return (-1);
  1114.       }
  1115.     
  1116.     if (n < 2)
  1117.       {
  1118.         if (n == 1)
  1119.           {
  1120.             close_infiles (ink, inp, n);
  1121.             fix_oddball_file_name (vRef0, generation_number, file_number);
  1122.           }
  1123.         strncpy (info + 1, "Beginning merge generation #", 28);
  1124.         i = 29 + putNum (info + 29, 2 + generation_number);
  1125.         info[0] = i - 1;
  1126.         give_msg (info);
  1127.         return (generation_number + 1);
  1128.       }
  1129.     
  1130.     outk = open_outkfile (vRef0, generation_number, file_number);
  1131.     outp = open_outpfile (vRef0, generation_number, file_number);
  1132.     
  1133.     inwords = 0;
  1134.     indistinctwords = 0;
  1135.     for (i = 0; i < n; ++i)
  1136.       {
  1137.         inwords += file_size (inp[i]) / sizeof(long);
  1138.         indistinctwords += file_size (ink[i]) / sizeof(KEY_REC);
  1139.       }
  1140.     
  1141.     nway_merge_kpfiles (ink, inp, outk, outp, n, zbufsiz);
  1142.     
  1143.     outdistinctwords = file_size (outk) / sizeof(KEY_REC);
  1144.  
  1145.     strncpy (info + 1, "Merge #", 7);
  1146.     i = 8 + putNum (info + 8, 1 + file_number / NMERGE);
  1147.     strncpy (info + i, ":  ", 3);
  1148.     i += 3;
  1149.     i += putNum (info + i, inwords);
  1150.     strncpy (info + i, " total words, ", 14);
  1151.     i += 14;
  1152.     i += putNum (info + i, indistinctwords);
  1153.     strncpy (info + i, " distinct words in, ", 20);
  1154.     i += 20;
  1155.     i += putNum (info + i, outdistinctwords);
  1156.     strncpy (info + i, " out.", 5);
  1157.     i += 5;
  1158.     info[0] = i - 1;
  1159.     give_msg (info);
  1160.     
  1161.     close_infiles (ink, inp, n);
  1162.     FSClose (outk);
  1163.     FSClose (outp);
  1164.     remove_used_infiles (n, vRef0, generation_number, file_number);
  1165.     
  1166.     return (generation_number);
  1167.   }
  1168.  
  1169. /* ------------file utility functions---------------------------- */
  1170.  
  1171. /* function to write out sorted k & p files based on the doc and ptr
  1172.  * arrays in memory....
  1173.  *
  1174.  * The kfile format is as described in detail elsewhere:
  1175.  *    the key word, turned into all capital letters and with spaces
  1176.  *        afterward, of fixed length KEY_LENGTH; and
  1177.  *    the cumulative count of how many words have passed before, including
  1178.  *        the current word, a long integer.
  1179.  *
  1180.  * Function revised 870907-... by ^z to use zbuffer method....
  1181.  */
  1182.  
  1183. long write_sorted_files (doc, ptr, nwords, offset, zbufsiz, pass_number,
  1184.                             vRef0)
  1185.   char *doc, **ptr;
  1186.   long nwords, offset, zbufsiz;
  1187.   int pass_number, vRef0;
  1188.   {
  1189.     int kfile, pfile;
  1190.     char *prev_word;
  1191.     KEY_REC *outk;
  1192.     long *outp, i;
  1193.     ZBUF zbuffer[2];
  1194.     
  1195.     if (nwords == 0)
  1196.         return;
  1197.     
  1198.     kfile = open_kfile (vRef0, pass_number);
  1199.     pfile = open_pfile (vRef0, pass_number);
  1200.     
  1201.     create_zbuffer (0, zbufsiz, kfile, sizeof(KEY_REC), zbuffer);
  1202.     create_zbuffer (1, zbufsiz, pfile, sizeof(long), zbuffer);
  1203.  
  1204.     prev_word = ptr[0];
  1205.     outk = (KEY_REC *)next_output_item (0, zbuffer);
  1206.     write_new_key (ptr[0], outk->kkey);
  1207.     
  1208.     for (i = 0; i < nwords; ++i)
  1209.       {
  1210.         if (is_new_word (prev_word, ptr[i]))
  1211.           {
  1212.             outk->ccount = i;
  1213.             outk = (KEY_REC *)next_output_item (0, zbuffer);
  1214.             write_new_key (ptr[i], outk->kkey);
  1215.             prev_word = ptr[i];
  1216.           }
  1217.         outp = (long *)next_output_item (1, zbuffer);
  1218.         *outp = (ptr[i] - doc) + offset;
  1219.       }
  1220.     outk->ccount = i;
  1221.  
  1222.     flush_zbuffer (0, zbuffer);
  1223.     flush_zbuffer (1, zbuffer);
  1224.     
  1225.     DisposPtr (zbuffer[0].zbufbase);
  1226.     DisposPtr (zbuffer[1].zbufbase);
  1227.     
  1228.     i = file_size (kfile) / sizeof(KEY_REC);
  1229.     FSClose (kfile);
  1230.     FSClose (pfile);
  1231.     
  1232.     return (i);
  1233.   }
  1234.  
  1235.  
  1236. /* function to determine if the current word is the same as or different
  1237.  * from the previous word -- if it is different, we'll need to write an
  1238.  * entry out to the key file kfile -- compare the words up to the first
  1239.  * '\0', or for a maximum distance of KEY_LENGTH, and return TRUE
  1240.  * if they differ, FALSE if they are identical that far.  Thus, a simple
  1241.  * call to zstrcmp() does the job.... but keep ours as a function instead
  1242.  * of a macro call for the moment, for safety and readability....
  1243.  */
  1244.  
  1245. int is_new_word (w0, w1)
  1246.   char *w0, *w1;
  1247.   {
  1248.     return (zstrcmp (w0, w1));
  1249.   }
  1250.  
  1251.  
  1252. /* function to write out a new key entry in the key_file:
  1253.  * KEY_LENGTH letters consisting of the key word (which will be found
  1254.  * delimited by a '\0'), followed by enough blanks to fill out the
  1255.  * record to total length KEY_LENGTH ...
  1256.  */
  1257.  
  1258. void write_new_key (p, kp)
  1259.   register char *p, *kp;
  1260.   {
  1261.     register int i, c;
  1262.  
  1263.     for (i = 0; i < KEY_LENGTH; ++i)
  1264.       {
  1265.         c = *p++;
  1266.         if (c == '\0')
  1267.             break;
  1268.         *kp++ = c;
  1269.       }
  1270.  
  1271.     for ( ; i < KEY_LENGTH; ++i)
  1272.         *kp++ = ' ';
  1273.     
  1274.     return;
  1275.   }
  1276.  
  1277.  
  1278. /* a very simple function to return the size of a file ... doesn't do any
  1279.  * error-checking -- sorry!
  1280.  */
  1281.  
  1282. long file_size (refnum)
  1283.   int refnum;
  1284.   {
  1285.     long result;
  1286.     
  1287.     GetEOF (refnum, &result);
  1288.     return (result);
  1289.   }
  1290.  
  1291. /* ---------------miscellaneous useful functions----------------- */
  1292.  
  1293. /* function to open an input key file for this generation and file number ...
  1294.  * note the limitation to no more than 9 generations, which with a 4-way
  1295.  * merge should be more than enough for a few years to come!  Note that
  1296.  * this function should return 0 and not give up if it attempts to open
  1297.  * a nonexistent file -- that's the signal for merge_indices() to know
  1298.  * that all of the input files have been used up....
  1299.  */
  1300.  
  1301. int open_inkfile (file_num, vRef0, generation_number)
  1302.   int file_num, vRef0, generation_number;
  1303.   {
  1304.     Str255 fname;
  1305.     int i;
  1306.     
  1307.     fname[1] = 'z';
  1308.     fname[2] = generation_number + '0';
  1309.     fname[3] = 'k';
  1310.     i = putNum ((char *)fname + 4, file_num);
  1311.     fname[0] = i + 3;
  1312.     
  1313.     if (FSOpen (fname, vRef0, &i) != noErr)
  1314.         return (NULL);
  1315.  
  1316.     return (i);
  1317.   }
  1318.  
  1319.  
  1320. /* function to open an input ptr file for this generation and file number
  1321.  */
  1322.  
  1323. int open_inpfile (file_num, vRef0, generation_number)
  1324.   int file_num, vRef0, generation_number;
  1325.   {
  1326.     Str255 fname;
  1327.     int i;
  1328.     
  1329.     fname[1] = 'z';
  1330.     fname[2] = generation_number + '0';
  1331.     fname[3] = 'p';
  1332.     i = putNum ((char *)fname + 4, file_num);
  1333.     fname[0] = i + 3;
  1334.     
  1335.     if (FSOpen (fname, vRef0, &i) != noErr)
  1336.         return (NULL);
  1337.  
  1338.     return (i);
  1339.   }
  1340.  
  1341.  
  1342. /* function to open an output key file for this generation and file number
  1343.  */
  1344.  
  1345. int open_outkfile (vRef0, generation_number, file_number)
  1346.   int vRef0, generation_number, file_number;
  1347.   {
  1348.     Str255 fname;
  1349.     int i;
  1350.     
  1351.     fname[1] = 'z';
  1352.     fname[2] = generation_number + 1 + '0';
  1353.     fname[3] = 'k';
  1354.     i = putNum ((char *)fname + 4, file_number / NMERGE);
  1355.     fname[0] = i + 3;
  1356.     if (Create (fname, vRef0, '????', 'CTLZ') != noErr)
  1357.       {
  1358.         give_msg ("\pSorry, fatal error creating merge key file -- click mouse to exit, then reboot!");
  1359.         beepWait ();
  1360.           RestoreA4();
  1361.         ExitToShell ();
  1362.       }
  1363.     
  1364.     if (FSOpen (fname, vRef0, &i) != noErr)
  1365.       {
  1366.         give_msg ("\pSorry, fatal error opening merge key file -- click mouse to exit, then reboot!");
  1367.         beepWait ();
  1368.           RestoreA4();
  1369.         ExitToShell ();
  1370.       }
  1371.  
  1372.     return (i);
  1373.   }
  1374.  
  1375.  
  1376. /* function to open an output ptr file for this generation and file number
  1377.  */
  1378.  
  1379. int open_outpfile (vRef0, generation_number, file_number)
  1380.   int vRef0, generation_number, file_number;
  1381.   {
  1382.     Str255 fname;
  1383.     int i;
  1384.     
  1385.     fname[1] = 'z';
  1386.     fname[2] = generation_number + 1 + '0';
  1387.     fname[3] = 'p';
  1388.     i = putNum ((char *)fname + 4, file_number / NMERGE);
  1389.     fname[0] = i + 3;
  1390.     if (Create (fname, vRef0, '????', 'CTLZ') != noErr)
  1391.       {
  1392.         give_msg ("\pSorry, fatal error creating merge ptr file -- click mouse to exit, then reboot!");
  1393.         beepWait ();
  1394.           RestoreA4();
  1395.         ExitToShell ();
  1396.       }
  1397.     
  1398.     if (FSOpen (fname, vRef0, &i) != noErr)
  1399.       {
  1400.         give_msg ("\pSorry, fatal error opening merge ptr file -- click mouse to exit, then reboot!");
  1401.         beepWait ();
  1402.           RestoreA4();
  1403.         ExitToShell ();
  1404.       }
  1405.  
  1406.     return (i);
  1407.   }
  1408.  
  1409.  
  1410. /* function to rename the remaining last unpaired key file & ptr file
  1411.  * from one generation to the next...
  1412.  */
  1413.  
  1414. void fix_oddball_file_name (vRef0, generation_number, file_number)
  1415.   int vRef0, generation_number, file_number;
  1416.   {
  1417.     Str255 oldname, newname;
  1418.     int i;
  1419.     
  1420.     oldname[1] = 'z';
  1421.     oldname[2] = generation_number + '0';
  1422.     oldname[3] = 'k';
  1423.     i = putNum ((char *)oldname + 4, file_number);
  1424.     oldname[0] = i + 3;
  1425.  
  1426.     newname[1] = 'z';
  1427.     newname[2] = generation_number + 1 + '0';
  1428.     newname[3] = 'k';
  1429.     i = putNum ((char *)newname + 4, file_number / NMERGE);
  1430.     newname[0] = i + 3;
  1431.     
  1432.     if (Rename (oldname, vRef0, newname) != noErr)
  1433.       {
  1434.         give_msg ("\pSorry, error renaming merge key file ... click mouse to continue");
  1435.         beepWait ();
  1436.       }
  1437.     
  1438.     oldname[1] = 'z';
  1439.     oldname[2] = generation_number + '0';
  1440.     oldname[3] = 'p';
  1441.     i = putNum ((char *)oldname + 4, file_number);
  1442.     oldname[0] = i + 3;
  1443.  
  1444.     newname[1] = 'z';
  1445.     newname[2] = generation_number + 1 + '0';
  1446.     newname[3] = 'p';
  1447.     i = putNum ((char *)newname + 4, file_number / NMERGE);
  1448.     newname[0] = i + 3;
  1449.     
  1450.     if (Rename (oldname, vRef0, newname) != noErr)
  1451.       {
  1452.         give_msg ("\pSorry, error renaming merge ptr file ... click mouse to continue");
  1453.         beepWait ();
  1454.       }
  1455.  
  1456.     return;
  1457.   }
  1458.  
  1459.  
  1460. /* function to give the final key and ptr files their proper ultimate
  1461.  * names ... ok for it to mess with doc_filename string....
  1462.  */
  1463.  
  1464. void fix_final_file_names (doc_filename, vRef0, generation_number)
  1465.   Str255 doc_filename;
  1466.   int vRef0, generation_number;
  1467.   {
  1468.     Str255 oldname;
  1469.     
  1470.     oldname[0] = 4;
  1471.     oldname[1] = 'z';
  1472.     oldname[2] = generation_number + '0';
  1473.     oldname[3] = 'k';
  1474.     oldname[4] = '0';
  1475.  
  1476.     doc_filename[++doc_filename[0]] = '.';
  1477.     doc_filename[++doc_filename[0]] = 'k';
  1478.     
  1479.     if (Rename (oldname, vRef0, doc_filename) != noErr)
  1480.       {
  1481.         give_msg ("\pSorry, error renaming final key file ... click mouse to continue");
  1482.         beepWait ();
  1483.       }
  1484.  
  1485.     oldname[3] = 'p';
  1486.     doc_filename[doc_filename[0]] = 'p';
  1487.  
  1488.     if (Rename (oldname, vRef0, doc_filename) != noErr)
  1489.       {
  1490.         give_msg ("\pSorry, error renaming final ptr file ... click mouse to continue");
  1491.         beepWait ();
  1492.       }
  1493.  
  1494.     return;
  1495.   }
  1496.  
  1497.  
  1498. /* function to get rid of the superfluous k & p files now that they
  1499.  * have been merged into the next generation....
  1500.  */
  1501.  
  1502. void remove_used_infiles (n, vRef0, generation_number, file_number)
  1503.   int n, vRef0, generation_number, file_number;
  1504.   {
  1505.     Str255 fname;
  1506.     int i, j;
  1507.     
  1508.     fname[1] = 'z';
  1509.     fname[2] = generation_number + '0';
  1510.     for (i = 0; i < n; ++i)
  1511.       {
  1512.         fname[3] = 'k';
  1513.         j = putNum ((char *)fname + 4, file_number + i);
  1514.         fname[0] = j + 3;
  1515.         
  1516.         if (FSDelete (fname, vRef0) != noErr)
  1517.           {
  1518.             give_msg ("\pSorry, error deletin merge key file ... click mouse to continue");
  1519.             beepWait ();
  1520.           }
  1521.  
  1522.         fname[3] = 'p';
  1523.         if (FSDelete (fname, vRef0) != noErr)
  1524.           {
  1525.             give_msg ("\pSorry, error deletin merge ptr file ... click mouse to continue");
  1526.             beepWait ();
  1527.           }
  1528.       }
  1529.     
  1530.     return;
  1531.   }
  1532.  
  1533.  
  1534. /* function to close out the ink and inp files that have been opened...
  1535.  */
  1536.  
  1537. void close_infiles (ink, inp, n)
  1538.   int ink[], inp[];
  1539.   int n;
  1540.   {
  1541.     int i;
  1542.     
  1543.     for (i = 0; i < n; ++i)
  1544.       {
  1545.         FSClose (ink[i]);
  1546.         FSClose (inp[i]);
  1547.       }
  1548.   }
  1549.  
  1550. /* mods 871211 for HyperCard XFCN work -- remove <stdio> stuff and
  1551.  * go to the Mac toolbox and HC system ... ^z
  1552.  */
  1553.  
  1554. /* functions to open files as needed in qndxr work...
  1555.  */
  1556.  
  1557.  
  1558. /* open the key file with proper name for this pass ... file will be
  1559.  * named "z0kN" where N represents the pass number ....
  1560.  */
  1561.  
  1562. int open_kfile (vRef0, pass_number)
  1563.   int vRef0, pass_number;
  1564.   {
  1565.     Str255 fname;
  1566.     int i;
  1567.     
  1568.     fname[1] = 'z';
  1569.     fname[2] = '0';
  1570.     fname[3] = 'k';
  1571.     i = putNum ((char *)fname + 4, pass_number);
  1572.     fname[0] = i + 3;
  1573.     
  1574.     if (Create (fname, vRef0, '????', 'CTLZ') != noErr)
  1575.       {
  1576.         give_msg ("\pSorry, fatal error creating key file -- click mouse to exit, then reboot!");
  1577.         beepWait ();
  1578.           RestoreA4();
  1579.         ExitToShell ();
  1580.       }
  1581.     
  1582.     if (FSOpen (fname, vRef0, &i) != noErr)
  1583.       {
  1584.         give_msg ("\pSorry, fatal error opening key file -- click mouse to exit, then reboot!");
  1585.         beepWait ();
  1586.           RestoreA4();
  1587.         ExitToShell ();
  1588.       }
  1589.  
  1590.     return (i);
  1591.   }
  1592.  
  1593.  
  1594. /* open the ptr file with proper name for this pass ... file will be
  1595.  * named "z0pN" where N represents the pass number ....
  1596.  */
  1597.  
  1598. int open_pfile (vRef0, pass_number)
  1599.   int vRef0, pass_number;
  1600.   {
  1601.     Str255 fname;
  1602.     int i;
  1603.     
  1604.     fname[1] = 'z';
  1605.     fname[2] = '0';
  1606.     fname[3] = 'p';
  1607.     i = putNum ((char *)fname + 4, pass_number);
  1608.     fname[0] = i + 3;
  1609.     if (Create (&fname, vRef0, '????', 'CTLZ') != noErr)
  1610.       {
  1611.         give_msg ("\pSorry, fatal error creating ptr file -- click mouse to exit, then reboot!");
  1612.         beepWait ();
  1613.           RestoreA4();
  1614.         ExitToShell ();
  1615.       }
  1616.     
  1617.     if (FSOpen (&fname, vRef0, &i) != noErr)
  1618.       {
  1619.         give_msg ("\pSorry, fatal error opening ptr file -- click mouse to exit, then reboot!");
  1620.         beepWait ();
  1621.           RestoreA4();
  1622.         ExitToShell ();
  1623.       }
  1624.  
  1625.     return (i);
  1626.   }
  1627.  
  1628.  
  1629. /* function to take the place of stdio's ftell()
  1630.  */
  1631.  
  1632. long zftell (refnum)
  1633.   int refnum;
  1634.   {
  1635.     long ans;
  1636.     
  1637.     GetFPos (refnum, &ans);
  1638.     return (ans);
  1639.   }
  1640.  
  1641. /* --------------function to do quicksort -------------------------- */
  1642.  
  1643. /*  sort elements "first" through "last" */
  1644.  
  1645. void zqsort (first, last)
  1646.   register char **first, **last;
  1647.   {
  1648.     register char **i, **j, *tmp;
  1649.  
  1650.     while (last - first > 1)
  1651.       {
  1652.         i = first;
  1653.         j = last;
  1654.         for (;;)
  1655.           {
  1656.             while (++i < last && compare_ptrs (i, first) < 0)
  1657.                 ;
  1658.             while (--j > first && compare_ptrs (j, first) > 0)
  1659.                 ;
  1660.             if (i >= j)
  1661.                  break;
  1662.              tmp = *i;
  1663.              *i = *j;
  1664.              *j = tmp;
  1665.           }
  1666.         tmp = *first;
  1667.         *first = *j;
  1668.         *j = tmp;
  1669.         if (j - first < last - (j + 1))
  1670.           {
  1671.             zqsort (first, j);
  1672.             first = j + 1;
  1673.           }
  1674.         else
  1675.           {
  1676.             zqsort (j + 1, last);
  1677.             last = j;
  1678.           }
  1679.       }
  1680.   }
  1681.  
  1682.  
  1683. /* function to compare two index ptrs and give a result appropriate
  1684.  * for quicksort to use in alphabetizing them....
  1685.  *
  1686.  * Since the words pointed to have already been turned into all capital
  1687.  * letters and delimiters have been filtered out, simply doing zstrcmp()
  1688.  * for KEY_LENGTH letters works fine!
  1689.  *
  1690.  * Slight modification to make the quicksort stable:  if two words tie,
  1691.  * then we want to compare their pointers to make the lesser one come
  1692.  * out first in the sort ...
  1693.  */
  1694.  
  1695. int compare_ptrs (p1, p2)
  1696.   register char **p1, **p2;
  1697.   {
  1698.     register int diff;
  1699.     
  1700.     diff = zstrcmp (*p1, *p2);
  1701.     if (diff == 0)
  1702.         diff = ((*p1 - *p2) > 0) ? 1 : -1;
  1703.     return (diff);
  1704.   }
  1705.  
  1706.  
  1707.  
  1708. /* my function to compare two strings and give a result as to who is
  1709.  * alphabetically earlier.  Note that this is almost the same as strncmp()
  1710.  * with the fixed value of KEY_LENGTH as the maximum comparison distance,
  1711.  * except that I must be sure to mask the characters to make them positive
  1712.  * (since we want to be able to handle the non-ASCII funny letters in
  1713.  * the Apple character set properly/consistently).  If the masking isn't
  1714.  * done, then inconsistent results can occur with those non-ASCII chars!
  1715.  */
  1716.  
  1717. int zstrcmp (s1, s2)
  1718.   register char *s1, *s2;
  1719.   {
  1720.     register int n = KEY_LENGTH;
  1721.     
  1722.     for (; --n && ((*s1 & 0xFF) == (*s2 & 0xFF)); s1++, s2++)
  1723.         if (!*s1) break;
  1724.         
  1725.     return ((*s1 & 0xFF) - (*s2 & 0xFF));
  1726.   }
  1727.  
  1728.